<head>
    <meta charset="UTF-8">
<title>算法训练 Xenia and String Problem</title>
<link rel="stylesheet" href="../css/main.css">
</head>
 <p>【问题描述】</p>
<div>Xenia去了IOI，拿到了一道字符串题。不幸的是，Xenia并不擅长字符串算法，请你帮助她解决这道题。</div>
<div>&nbsp;</div>
<div>字符串s是一个由字符s[1]s[2]...s[|s|]组成的序列，|s|表示字符串的长度。</div>
<div>子串s[i...j]是s[i]s[i+1]...s[j]构成的字符串。</div>
<div>&nbsp;</div>
<div>如果字符串s满足以下条件，那么就称它为Gray串：</div>
<div>(1)串长|s|是奇数；</div>
<div>(2)字符s[(|s|+1)/2]在串s中只出现了一次；</div>
<div>(3)|s|=1或子串s[1...(|s|+1)/2-1]和子串s[(|s|+1)/2+1...|s|]相同且都是Gray串。</div>
<div>&nbsp;</div>
<div>比如，串&quot;abacaba&quot;,&quot;xzx&quot;,&quot;g&quot;都是Gray串，而串&quot;xz&quot;,&quot;abaxcbc&quot;则不是。</div>
<div>&nbsp;</div>
<div>定义一个串p的美丽值为所有串p的子串中，是Gray串的子串的长度的平方和。</div>
<div>也就是说，对于所有数对(i,j)满足(1&le;i&le;j&le;|p|)且子串p[i...j]是Gray串，就把(j-i+1)^2加到美丽值中。</div>
<div>&nbsp;</div>
<div>Xenia已经得到了一个由小写英文字母构成的串t，她被允许修改串t中最多一个字符(也可以不修改)，来使得串t的美丽值最大。</div>
<div>你的任务就是求出串t修改后的最大美丽值。</div>
<p>【输入格式】<br />
一行，一个由小写英文字母构成的字符串t。<br />
【输出格式】<br />
一行，一个正整数，为串t修改后的最大美丽值。<br />
【样例输入】<br />
zzz<br />
【样例输出】<br />
12<br />
【数据规模和约定】</p>
<div>5%的数据，|t|&le;10。</div>
<div>20%的数据，|t|&le;100。</div>
<div>40%的数据，|t|&le;1000。</div>
<div>100%的数据，|t|&le;10^5。</div>